//Given a collection of candidate numbers (candidates) and a target number (targ
//et), find all unique combinations in candidates where the candidate numbers sum 
//to target. 
//
// Each number in candidates may only be used once in the combination. 
//
// Note: The solution set must not contain duplicate combinations. 
//
// 
// Example 1: 
//
// 
//Input: candidates = [10,1,2,7,6,1,5], target = 8
//Output: 
//[
//[1,1,6],
//[1,2,5],
//[1,7],
//[2,6]
//]
// 
//
// Example 2: 
//
// 
//Input: candidates = [2,5,2,1,2], target = 5
//Output: 
//[
//[1,2,2],
//[5]
//]
// 
//
// 
// Constraints: 
//
// 
// 1 <= candidates.length <= 100 
// 1 <= candidates[i] <= 50 
// 1 <= target <= 30 
// 
// Related Topics 数组 回溯算法 
// 👍 579 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//Java：Combination Sum II
class P40CombinationSumIi {
    public static void main(String[] args) {
        Solution solution = new P40CombinationSumIi().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> result = new ArrayList<>();

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            combinationSum(candidates, 0, 0, target, new ArrayList<Integer>());
            return result;
        }

        private void combinationSum(int[] candidates, int start, int depth, int target, List<Integer> list) {
            for (int j = start; j < candidates.length; j++) {
                int candidate = candidates[j];
                if (target - candidate < 0) {
                    return;
                }
                if (target - candidate == 0) {
                    list.add(candidate);
                    if (result.contains(list) != true) {
                        result.add(new ArrayList<>(list));
                    }
                    list.remove(list.size() - 1);
                    return;
                } else if (target > 0) {
                    list.add(candidate);
                    combinationSum(candidates, start + 1, depth + 1, target - candidate, list);
                    list.remove(list.size() - 1);
                    start += 1;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}